исследование задачи о максимальном потоке

Введение
Необходимость решения проблем различной сложности, возникающих в разнообразных сферах деятельности, вызвала к жизни множество своих приемов, методов, подходов решения этих проблем. В рамках практической и теоретической деятельности формировались системные взгляды на методологию исследования сложных технических, природных и социальных систем. Наука, в рамках которой получили развитие исследования сложных систем, получила название «теория систем» – «системный подход» – «системный анализ».
Методы и модели для решения задач, в которых необходимая информация однозначна и достоверна, называются детерминированными. Линейное программирование – это раздел науки «Математическое программирование», применяемый при разработке методов отыскания экстремума (максимума или минимума) линейной функции нескольких переменных при линейных ограничениях, наложенных на эти переменные.
Тема данной курсовой работы: “ Исследование задачи о максимальном потоке”. Эта задача относится к классу задач линейного программирования транспортного типа.
В данной работе будут рассмотрены теоретические основы построения подобных задач, а также решена практическая задача нахождения максимального потока.
Будет рассмотрен пошаговый алгоритм реализации метода решения и последовательный проход по этому алгоритму.
Данная задача будет решаться вручную без использованием специализированного программного обеспечения.
Цель данной работы – найти оптимальное решение предлагаемой задачи нахождения максимального потока в сети, а также изучить методику решения подобных задач.
Задачи данной работы:
1) Изучить теоретические основы задачи о максимальном потоке.
2) Разобраться с работой алгоритма пошагового решения данной задачи.
3) Рассмотреть пример решения подобных задач.
4) Произвести постановку задачи.
5) Решить предложенную задачу с помощью изученной методологии решения.



1. Теоретические основы исследования задачи о максимальном потоке
Рассмотрим сеть, имеющую только один источник s и только один сток t. Рассмотрим задачу о потоке из узла s в узел t, причем s и t могут быть связаны произвольно сложной промежуточной сетью. Задача о максимальном потоке состоит в определении количества, которое можно перевезти из s в t. Формализуем эти понятия.
Узел s множества R называется источником потока f, если ; узел t называется стоком потока f, если ; узел х называется нейтральным, если . Поток с одним источником s и стоком t называется потоком от s к t. При всех (все, что «вытекает» из источника, попадает в сток). Мощностью потока f называется число . Поток наибольшей мощности носит название максимального потока. Сечением (или разрезом) сети относительно s и t называется разбиение узлов R на такие два множества и , что , , . Пропускной способностью сечения называется величина (сумма пропускных способностей дуг, начала которых находятся в S, а концы – в ).
Сечение с наименьшей пропускной способностью называется минимальным сечением. Связь между сечениями и потоками устанавливается следующей леммой.
Лемма. Если f – поток в сети от s к t и – сечение в сети G, то мощность потока f не превосходит , т. е.
.
Доказательство.
.
Замечание. Если имеет место равенство, то сразу можно сделать вывод о максимальном потоке f и минимальном сечении .
Теорема о максимальном потоке и минимальном сечении. Для любой сети величина максимального потока из s в t равна пропускной способности минимального сечения, отделяющего s от t.
Доказательство. Пусть – максимальный поток. Такой поток существует, потому что в сети из-за ограничений допустимости и требования целочисленности имеется лишь конечное множество потоков.
Будем говорить, что ребро насыщенно потоком , если . Определим сечение следующим образом. Узел , если или если существует ненасыщенный путь от s к х, т. е. последовательность ребер , , …, , ни одно из которых не является насыщенным. За берется, как обычно, дополнение множества S. Чтобы показать, что – сечение, нужно установить лишь принадлежность t к . Но если бы , то имелся бы ненасыщенный путь Р из s в t, т. е. для всех ребер . Тогда, если положить

то можно определить новый поток , для которого

Отсюда следует, что мощность больше мощности , а не , что противоречит максимальности потока .
Теперь можно показать, что в соотношении имеет место равенство. Действительно, если бы было

то для некоторых и оказалось бы . С другой стороны, из определения S следует, что имеется ненасыщенный путь от s к x. Так как ребро также ненасыщено, то можно продолжить ненасыщенный путь от s к у, что противоречит . Следовательно, неравенство (14.8) невозможно и теорема доказана.